import java.util.Scanner;

/**
 * @author yu
 * @date 2025年04月28日 22:50
 * @Description: 188. 买卖股票的最佳时机 IV
 * 给你一个整数数组 prices 和一个整数 k ，其中 prices[i] 是某支给定的股票在第 i 天的价格。
 * 设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。
 * 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
 * 示例 1：
 * 输入：k = 2, prices = [2,4,1]
 * 输出：2
 * 解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。
 */
public class _09_dp_27_188maxProfit {
    /*动态规划*/
    public static int maxProfit5(int k, int[] prices) {
        if (prices.length == 0) return 0;

        // [天数][股票状态]
        // 股票状态: 奇数表示第 k 次交易持有/买入, 偶数表示第 k 次交易不持有/卖出, 0 表示没有操作
        int len = prices.length;
        int[][] dp = new int[len][k*2 + 1];

        // dp数组的初始化, 与版本一同理
        for (int i = 1; i < k*2; i += 2) {
            dp[0][i] = -prices[0];
        }

        for (int i = 1; i < len; i++) {
            for (int j = 0; j < k*2 - 1; j += 2) {
                dp[i][j + 1] = Math.max(dp[i - 1][j + 1], dp[i - 1][j] - prices[i]);
                dp[i][j + 2] = Math.max(dp[i - 1][j + 2], dp[i - 1][j + 1] + prices[i]);
            }
        }
        return dp[len - 1][k*2];
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("请输入最大交易次数 k：");
        int k = sc.nextInt();
        sc.nextLine(); // 消耗掉 nextInt() 后的换行符

        System.out.println("请输入股票价格，以空格分隔：");
        String input = sc.nextLine();
        String[] priceStrs = input.split(" ");
        int[] prices = new int[priceStrs.length];
        for (int i = 0; i < priceStrs.length; i++) {
            prices[i] = Integer.parseInt(priceStrs[i]);
        }

        int profit5 = maxProfit5(k, prices);
        System.out.println("使用动态规划算法得到的最大利润: " + profit5);
        sc.close();
    }
}
